package 数据结构.树;

import java.util.Stack;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-03
 */

public class JZ33二叉搜索树的后序遍历序列 {
    //栈 后序== 左右根
    //倒序输出的时候是：根→右→左，其中左子节点的值恒小于根和右，于是便有遍历满足条件：
        //①递增时候无任何问题
        //②递减时候要求必须小于以前所有数。
    //依次为条件，先遍历入栈，再在递减时出栈对比即可。
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 处理序列为空情况
        if(sequence.length == 0) return false;
        Stack<Integer> s = new Stack<>();
        int root = Integer.MAX_VALUE;
        // 以根，右子树，左子树顺序遍历
        //【1 3 2 5 4】
        for(int i = sequence.length - 1; i >= 0; i--) {
            // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，
            // 左子树的节点如果>root则说明违背二叉搜索的性质
            if(sequence[i] > root) return false;
            // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root
            while(!s.isEmpty() && s.peek() > sequence[i]) {
                root = s.pop();
            }
            // 每个数字都要进一次栈
            s.add(sequence[i]);
        }
        return true;
    }

    //二叉树递归
    public boolean VerifySquenceOfBST2(int [] sequence) {
        if(sequence.length == 0) return false;
        return order(sequence, 0, sequence.length - 1);
    }

    boolean order(int [] sequence, int l, int r){
        // 剩一个节点的时候 返回 true
        if(l >= r) return true;

        int j;
        int mid = sequence[r];

        // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
        for(j = r; j >= l; j--) {
            int cur = sequence[j];
            if(cur < mid) break;
        }

        // 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
        for(int i = j; i >= l; i--) {
            int cur = sequence[i];
            if(cur > mid) return false;
        }
        return order(sequence, l, j) && order(sequence, j+1, r-1);
    }
}
